Search results for " Turing"

Hartmanis-Stearns Conjecture on Real Time and Transcendence

2012

Hartmanis-Stearns conjecture asserts that any number whose decimal expansion can be computed by a multitape Turing machine is either rational or transcendental. After half a century of active research by computer scientists and mathematicians the problem is still open but much more interesting than in 1965.

Positive Versions of Polynomial Time

1998

Abstract We show that restricting a number of characterizations of the complexity class P to be positive (in natural ways) results in the same class of (monotone) problems, which we denote by posP . By a well-known result of Razborov, posP is a proper subclass of the class of monotone problems in P . We exhibit complete problems for posP via weak logical reductions, as we do for other logically defined classes of problems. Our work is a continuation of research undertaken by Grigni and Sipser, and subsequently Stewart; indeed, we introduce the notion of a positive deterministic Turing machine and consequently solve a problem posed by Grigni and Sipser.

One-Counter Verifiers for Decidable Languages

2013

Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working memory, i.e. replacing the working tape(s) with a single counter, we can define some IPS’s for each decidable language. Such verifiers are called two-way probabilistic one-counter automata (2pca’s). Then, we show that by adding a fixed-size quantum memory to a 2pca, called a two-way one-counter automaton with quantum and classical states (2qcca), the protocol can be spac…

Cross-diffusion effects on stationary pattern formation in the FitzHugh-Nagumo model

2022

<p style='text-indent:20px;'>We investigate the formation of stationary patterns in the FitzHugh-Nagumo reaction-diffusion system with linear cross-diffusion terms. We focus our analysis on the effects of cross-diffusion on the Turing mechanism. Linear stability analysis indicates that positive values of the inhibitor cross-diffusion enlarge the region in the parameter space where a Turing instability is excited. A sufficiently large cross-diffusion coefficient of the inhibitor removes the requirement imposed by the classical Turing mechanism that the inhibitor must diffuse faster than the activator. In an extended region of the parameter space a new phenomenon occurs, namely the exis…

A Logical Characterisation of Linear Time on Nondeterministic Turing Machines

1999

The paper gives a logical characterisation of the class NTIME(n) of problems that can be solved on a nondeterministic Turing machine in linear time. It is shown that a set L of strings is in this class if and only if there is a formula of the form ∃f1..∃fk∃R1..∃Rm∀xφv; that is true exactly for all strings in L. In this formula the fi are unary function symbols, the Ri are unary relation symbols and φv; is a quantifierfree formula. Furthermore, the quantification of functions is restricted to non-crossing, decreasing functions and in φv; no equations in which different functions occur are allowed. There are a number of variations of this statement, e.g., it holds also for k = 3. From these r…

Minimal nontrivial space complexity of probabilistic one- way turing machines

2005

Languages recognizable in o(log log n) space by probabilistic one — way Turing machines are proved to be regular. This solves an open problem in [4].

Quantum Computation With Devices Whose Contents Are Never Read

2010

In classical computation, a "write-only memory" (WOM) is little more than an oxymoron, and the addition of WOM to a (deterministic or probabilistic) classical computer brings no advantage. We prove that quantum computers that are augmented with WOM can solve problems that neither a classical computer with WOM nor a quantum computer without WOM can solve, when all other resource bounds are equal. We focus on realtime quantum finite automata, and examine the increase in their power effected by the addition of WOMs with different access modes and capacities. Some problems that are unsolvable by two-way probabilistic Turing machines using sublogarithmic amounts of read/write memory are shown to…

Turing Instability and Pattern Formation for the Lengyel–Epstein System with Nonlinear Diffusion

2014

In this work we study the effect of density dependent nonlinear diffusion on pattern formation in the Lengyel---Epstein system. Via the linear stability analysis we determine both the Turing and the Hopf instability boundaries and we show how nonlinear diffusion intensifies the tendency to pattern formation; in particular, unlike the case of classical linear diffusion, the Turing instability can occur even when diffusion of the inhibitor is significantly slower than activator's one. In the Turing pattern region we perform the WNL multiple scales analysis to derive the equations for the amplitude of the stationary pattern, both in the supercritical and in the subcritical case. Moreover, we c…

Intelligenza artificiale

2009

Chemical self-organization in self-assembling biomimetic systems

2009

Abstract Far-from-equillibrium oscillating chemical reactions are among the simplest systems showing complex behaviors and emergent properties. This class of reactions is often employed to mimic and understand the mechanisms of a great variety of biological processes. In this context, pattern formation due to the coupling between reaction and transport phenomena represent an active and promising research area. In this paper, we present results coming from experiments where we tried to blend the structural properties of self-assembled matrixes (sodium dodecyl sulphate micelles and phospholipid bilayers) together with the evolutive peculiarities of the Belousov–Zhabotinsky reaction. A series …